// write your code here cpp
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int f[N];
int main()
{
	f[1] = 1, f[2] = 2;
	for (int i = 3;i <= N;i++)
	{
		f[i] = (f[i - 1] + f[i - 2]) % 1000000;
	}
	while (cin >> n)
	{
		if (n <= 25)
			cout << f[n] << endl;
		else
			printf("%06d\n", f[n]);
	}
	return 0;
}